CF700E Cool Slogans 解题报告

Description

给定长度为 nn 的字符串 s ,要求构造字符串序列 s1,s2,,sks_1,s_2,\cdots,s_k ,满足 i[1,k]\forall i\in[1,k]sis_i 是 s 的子串,且 i[2,k]\forall i\in[2,k], 都有 si1s_{i-1}sis_i 中至少出现了两次(可以有重叠部分)。sis_i 不能为空。求最大的 kk 值。
1n2×1051\leq n\leq 2\times 10^5

Solution

阅读全文 »

[SHOI2014]三叉神经树 解题报告

Description

给定一棵以 11 为根的有 3n+13n+1 个节点的树,树上每个节点均有一个输出端。树上有 nn 个节点有 33 个子节点,其余的 2n+12n+1 个节点无子节点(也就是叶子)。2n+12n+1 个节点的初始值均为 0/10/1 ,并且已经提前知道;剩余 nn 个节点的值为其 33 个子节点中出现次数最多的值。qq 次询问,每次改变一个叶子节点的值,求操作后根节点的值。
n,q5×105n,q\leq 5\times 10^5

Solution

阅读全文 »

[NOI2018]你的名字 解题报告

Description

给定字符串 s 。有 qq 个询问,每个询问形如 t l rt\ l\ r ,表示查询字符串 t 中有多少个本质不同的子串在 s[l:r]出现过。
q,s,t5×105q,|s|,|t|\leq 5\times 10^5

Solution

阅读全文 »

CF526D Om Nom and Necklace 解题报告

Description

给定长度为 n 的字符串 s ,对于 s 的每个前缀,求该前缀是否能满足 AB...ABA 的形式,其中 A 恰好有 k+1 个,B 恰好有 k 个 。A B 可以是任意字符串,或者为空串;k 是给定的。
1n,k1061\leq n,k\leq 10^6

Solution

阅读全文 »

Luogu4173 残缺的字符串 解题报告

Description

给定长度为 n 的字符串 A 和长度为 m 的字符串 B 。当以 A 为模式串时,你希望求出对于 B 的每一个位置 i ,从该位置开始的连续 n 个字符形成的子串是否能与 A 完全匹配。A B 中可能含有通配符 @ 。通配符可以视作为任意小写字母。
1nm3×1051\leq n\leq m\leq 3\times 10^5

Solution

阅读全文 »

[HNOI2004]L语言 解题报告

Description

给定一个由 n 个字符串 s 组成的字典,再给定 m 句话 t ,求每句话在该字典下可以理解的最长前缀。
n20,m50,s10,t2×106n\leq 20,m\leq 50,|s|\leq 10,|t|\leq 2\times 10^6

Solution

阅读全文 »

[HAOI2009]求回文串 解题报告

Description

给定长度为 n 的字符串 s ,每次只能交换相邻两个位置。求使得 s 为回文串的最小交换次数。无解输出 -1 。
n106n\leq 10^6,保证都是大写字母

Solution

阅读全文 »

PAM 学习笔记

回文自动机(PAM)是针对给定串,包含了该串所有回文子串的信息的自动机。
PAM 的每个节点代表了一个本质不同的回文子串,记 s[p] 为点 p 代表的回文子串。
PAM 的每个节点有三个基础属性:fail/len/child 。
len:a[p].len 表示 s[p] 的长度。

阅读全文 »